home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2001 May / SGI IRIX Base Documentation 2001 May.iso / usr / share / catman / p_man / cat3 / librw / RWBinaryTree.z / RWBinaryTree
Encoding:
Text File  |  1998-10-30  |  12.2 KB  |  331 lines
  1.  
  2.  
  3.  
  4. RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                          RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  5.  
  6.  
  7.  
  8. NNNNaaaammmmeeee
  9.      RWBinaryTree - Rogue Wave library class
  10.  
  11. SSSSyyyynnnnooooppppssssiiiissss
  12.               typedef RWBinaryTree SortedCollection;   // Smalltalk typedef.
  13.  
  14.  
  15.  
  16.               #include <rw/bintree.h>
  17.           RWBinaryTree bt;
  18.  
  19.  
  20.  
  21.  
  22. DDDDeeeessssccccrrrriiiippppttttiiiioooonnnn
  23.      Class RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee represents a group of ordered elements, internally
  24.      sorted by the ccccoooommmmppppaaaarrrreeeeTTTToooo(((()))) function.  Duplicates are allowed.  An object
  25.      stored by an RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee must inherit abstract base class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  26.  
  27. PPPPeeeerrrrssssiiiisssstttteeeennnncccceeee
  28.      Polymorphic
  29.  
  30. PPPPuuuubbbblllliiiicccc CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrrssss
  31.               RWBinaryTree();
  32.  
  33.  
  34.      Construct an empty sorted collection.
  35.  
  36.               RWBinaryTree(const RWBinaryTree& t);
  37.  
  38.  
  39.      Copy constructor.  Constructs a shallow copy from tttt.  Member function
  40.      bbbbaaaallllaaaannnncccceeee(((()))) (see below) is called before returning.
  41.  
  42.               virtual ~RWBinaryTree();
  43.  
  44.  
  45.      Redefined from RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Calls cccclllleeeeaaaarrrr(((()))).
  46.  
  47. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr OOOOppppeeeerrrraaaattttoooorrrrssss
  48.               void
  49.           ooooppppeeeerrrraaaattttoooorrrr====(const RWBinaryTree& bt);
  50.  
  51.  
  52.      Sets self to a shallow copy of bbbbtttt.
  53.  
  54.               void
  55.           ooooppppeeeerrrraaaattttoooorrrr++++====(const RWCollection ct);
  56.  
  57.  
  58.      Inserts each element of ....cccctttt into self.  Note that using this operator to
  59.      insert an already-sorted collection will result in creating a very
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                          RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  71.  
  72.  
  73.  
  74.      unbalanced tree, possibly to the point of stack overflow.
  75.  
  76.               RWBoolean
  77.           ooooppppeeeerrrraaaattttoooorrrr<<<<====(const RWBinaryTree& bt) const;
  78.  
  79.  
  80.      Returns TTTTRRRRUUUUEEEE if self is a subset of the collection bbbbtttt.  That is, every
  81.      item in self must compare equal to a unique item in bbbbtttt.
  82.  
  83.               RWBoolean
  84.           ooooppppeeeerrrraaaattttoooorrrr========(const RWBinaryTree& bt) const;
  85.  
  86.  
  87.      Returns TTTTRRRRUUUUEEEE if self and bbbbtttt are equivalent.  That is, they must have the
  88.      same number of items and every item in self must compare equal to a
  89.      unique item in bbbbtttt.
  90.  
  91. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr FFFFuuuunnnnccccttttiiiioooonnnnssss
  92.               virtual void
  93.           aaaappppppppllllyyyy(RWapplyCollectable ap, void*);
  94.  
  95.  
  96.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn to apply the user-supplied function
  97.      pointed to by aaaapppp to each member of the collection, in order, from
  98.      smallest to largest.  This supplied function should not do anything to
  99.      the items that could change the ordering of the collection.
  100.  
  101.               void
  102.           bbbbaaaallllaaaannnncccceeee();
  103.  
  104.  
  105.      Special function to balance the tree.  In a perfectly balanced binary
  106.      tree with no duplicate elements, the number of nodes from the root to any
  107.      external (leaf) node differs by at most one node.  Since this collection
  108.      allows duplicate elements, a perfectly balanced tree is not always
  109.      possible.  Preserves the order of duplicate elements.
  110.  
  111.               virtual RWspace
  112.           bbbbiiiinnnnaaaarrrryyyySSSSttttoooorrrreeeeSSSSiiiizzzzeeee() const;
  113.  
  114.  
  115.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  116.  
  117.               virtual void
  118.           cccclllleeeeaaaarrrr();
  119.  
  120.  
  121.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  122.  
  123.               virtual void
  124.           cccclllleeeeaaaarrrrAAAAnnnnddddDDDDeeeessssttttrrrrooooyyyy();
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                          RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  137.  
  138.  
  139.  
  140.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  141.  
  142.               virtual int
  143.           ccccoooommmmppppaaaarrrreeeeTTTToooo(const RWCollectable* a) const;
  144.  
  145.  
  146.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  147.  
  148.               virtual RWBoolean
  149.           ccccoooonnnnttttaaaaiiiinnnnssss(const RWCollectable* target) const;
  150.  
  151.  
  152.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  153.  
  154.               virtual size_t
  155.           eeeennnnttttrrrriiiieeeessss() const;
  156.  
  157.  
  158.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  159.  
  160.               virtual RWCollectable*
  161.           ffffiiiinnnndddd(const RWCollectable* target) const;
  162.  
  163.  
  164.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Returns the first item that compares
  165.      equal to the item pointed to by ttttaaaarrrrggggeeeetttt, or nnnniiiillll if no item was found.
  166.  
  167.               virtual unsigned
  168.           hhhhaaaasssshhhh() const;
  169.  
  170.  
  171.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  172.  
  173.               unsigned
  174.           hhhheeeeiiiigggghhhhtttt() const;
  175.  
  176.  
  177.      Returns the number of nodes between the root node and the farthest leaf.
  178.      A RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee with one entry will have a height of 1.  Note that the
  179.      entire tree is traversed to discover this value.
  180.  
  181.               virtual RWCollectable*
  182.           iiiinnnnsssseeeerrrrtttt(RWCollectable* c);
  183.  
  184.  
  185.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Inserts the item cccc into the
  186.      collection and returns it.  Returns nnnniiiillll if the insertion was
  187.      unsuccessful.  The item cccc is inserted according to the value returned by
  188.      ccccoooommmmppppaaaarrrreeeeTTTToooo(((()))). iiiinnnnsssseeeerrrrtttt(((()))) does not automatically balance the RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee....
  189.      Be careful not to iiiinnnnsssseeeerrrrtttt(((()))) a long sequence of sorted items without
  190.      calling bbbbaaaallllaaaannnncccceeee(((()))) since the result will be very unbalanced (and therefore
  191.      inefficient).
  192.  
  193.  
  194.  
  195.                                                                         PPPPaaaaggggeeee 3333
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                          RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  203.  
  204.  
  205.  
  206.               virtual RWClassID
  207.           iiiissssAAAA() const;
  208.  
  209.  
  210.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee to return ________RRRRWWWWBBBBIIIINNNNAAAARRRRYYYYTTTTRRRREEEEEEEE.
  211.  
  212.               virtual RWBoolean
  213.           iiiissssEEEEmmmmppppttttyyyy() const;
  214.  
  215.  
  216.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  217.  
  218.               virtual RWBoolean
  219.           iiiissssEEEEqqqquuuuaaaallll(const RWCollectable* a) const;
  220.  
  221.  
  222.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  223.  
  224.               virtual size_t
  225.           ooooccccccccuuuurrrrrrrreeeennnncccceeeessssOOOOffff(const RWCollectable* target) const;
  226.  
  227.  
  228.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Returns the number of items that
  229.      compare equal to the item pointed to by ttttaaaarrrrggggeeeetttt.
  230.  
  231.               virtual RWCollectable*
  232.           rrrreeeemmmmoooovvvveeee(const RWCollectable* target);
  233.  
  234.  
  235.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Removes the first item that compares
  236.      equal to the object pointed to by ttttaaaarrrrggggeeeetttt and returns it.  Returns nnnniiiillll if
  237.      no item was found.
  238.  
  239.               virtual void
  240.           rrrreeeemmmmoooovvvveeeeAAAAnnnnddddDDDDeeeessssttttrrrrooooyyyy(const RWCollectable* target);
  241.  
  242.  
  243.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  244.  
  245.               virtual void
  246.           rrrreeeessssttttoooorrrreeeeGGGGuuuuttttssss(RWvistream&);
  247.           virtual void
  248.           rrrreeeessssttttoooorrrreeeeGGGGuuuuttttssss(RWFile&);
  249.  
  250.  
  251.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  252.  
  253.               virtual void
  254.           ssssaaaavvvveeeeGGGGuuuuttttssss(RWvostream&) const;
  255.           virtual void
  256.           ssssaaaavvvveeeeGGGGuuuuttttssss(RWFile&) const;
  257.  
  258.  
  259.  
  260.  
  261.                                                                         PPPPaaaaggggeeee 4444
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268. RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                          RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  269.  
  270.  
  271.  
  272.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn to store objects by level, rather than
  273.      in order.  This results in the tree maintaining its morphology.
  274.  
  275.               RWStringID
  276.           ssssttttrrrriiiinnnnggggIIIIDDDD();
  277.  
  278.  
  279.      (acts virtual) Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  280.  
  281.  
  282.  
  283.  
  284.  
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.                                                                         PPPPaaaaggggeeee 5555
  328.  
  329.  
  330.  
  331.